The disclosed invention relates generally to resource allocation in network elements of a communications network, and more specifically to a system for allocating resources to virtual connections in a network switch.
Communications networks interconnect end stations through paths including multiple devices or systems referred to as network elements. Network elements may include devices known as switches, bridges and routers. It is sometimes necessary to ensure a maximum end to end delay and a maximum end to end delay variation for data units transferred along a path between two end stations. For example, when a user at a first end station (end station A) requests that a virtual connection be established with a second end station (end station B), the request may include certain Quality of Service (QoS) parameters specifying performance levels that must be met by any resulting connection. In an Asynchronous Transfer Mode (ATM) environment, such QoS parameters include "Maximum Cell Transfer Delay" (Max CTD), and "Maximum Cell Delay Variation" (Max CDV). The Max CTD parameter defines an upper limit for total delay permitted for cells transmitted over the requested connection. The Max CDV parameter defines the maximum permitted variation between cell transfer delays over the requested connection.
In the above example, end station A will attempt to establish a path to end station B on which sufficient resources are available in each network element along the path to support the QoS parameters associated with a given request. If such resources are available, then each network element along the path reserves resources for the connection, and the connection is established.
The various kinds of delay that may be experienced by a data unit may be thought of as falling into three categories: 1) link propagation delay (LPD), 2) switching delay (SD), and 3) queuing delay (QD). The end to end LPD for a given path is the sum of the delays encountered by a data unit on the links for a given path. The end to end LPD does not include the time a data unit may be delayed within a network element. Switching delay is the time required to pass a data unit between an input port and an output port within a switch, assuming no queuing delays due to traffic congestion. Accordingly, switching delay is a function of the inherent speed of a particular switch. Queuing delay is the delay resulting from a data unit being stored in an input or output queue within a network element, and is dependant on the congestion being experienced by that network element at a specific point in time. Thus, actual delay and delay variation reflect both resource capacity and utilization at each network element that is traversed by a data unit within a given path through a network.
In existing systems, when a network element receives a request to establish a connection, the network element will reserve resources to be used to support the connection if the connection request is granted. However, existing systems test potential paths using a mechanism which passes only the maximum permitted delay, maximum permitted delay variation, and accumulated delay to each of the network elements in the path as the path is being tested. While these parameters are sufficient to determine whether a path should be eliminated from consideration due to insufficient resources, such systems fail to provide adequate information for each network element in the path to reserve resources accurately in order to meet the specific needs of a given connection. As a result, resources may be under or over allocated to a connection because the network elements cannot accurately determine the amount of resources that should be allocated.
For the reasons stated above, it would be desirable to have a system for allocating resources to a virtual connection along a path through a communications network which more accurately provides information to network elements along the path, such that resources are not over or under allocated. The system should permit network elements along the path to satisfy a connection request by accurately allocating resources in response to characteristics of the path being tested. The system should further be convenient to implement and compatible with existing systems.